Weighted Graph

Definition / 定义

加权图：一种图（由顶点与边组成），其中每条边（有时也包括顶点）都带有一个数值“权重”，常用来表示距离、成本、时间、容量、概率等，用于求最短路、最小生成树等问题。（也存在“无权图”等其他类型。）

Pronunciation / 发音

/ˈweɪtɪd ɡræf/

Examples / 例句

A weighted graph helps us find the cheapest route between cities.
加权图可以帮助我们找到城市之间成本最低的路线。

In the weighted graph, Dijkstra’s algorithm computes the shortest path by comparing cumulative edge weights rather than just counting edges.
在加权图中，Dijkstra 算法通过比较路径上边权重的累计值来计算最短路径，而不是只数边的条数。

Etymology / 词源

weighted 来自 weight（重量、权重），表示“带权的、赋予权值的”；graph 在数学中指“图（由点与线/边构成的结构）”。合在一起，“weighted graph”字面义即“带有权值的图”，是算法与离散数学中的常用术语。

Related Words / 相关词

• Graph
• Vertex
• Edge
• Weight
• Path
• Shortest Path
• Dijkstra
• Minimum Spanning Tree

Literary Works / 文学作品

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein）：在最短路径、最小生成树等章节中系统使用“weighted graph”等表述。
• The Algorithm Design Manual（Steven S. Skiena）：在图算法与实际建模（成本/距离）语境中频繁出现。
• Graph Theory（Reinhard Diestel）：以严格数学语言讨论带权/赋权结构（常以“weighted”或“edge-weighted”表述）。